/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/classical-binary-search
   @Language: C++
   @Datetime: 17-04-01 21:17
   */

// Method 1, Using Operator [] to access vector elements, Time 2250ms
class Solution {
public:
	/**
	 * @param A an integer array sorted in ascending order
	 * @param target an integer
	 * @return an integer
	 * Tip: See problem 14, first-position-of-target
	 */
	int findPosition(vector<int>& A, int target) {
		// Write your code here
		int begin=0, end=A.size(), mid=0;
		while(begin<end){
			mid = begin+(end-begin)/2;
			if (A[mid]>=target) end = mid;
			else begin = mid+1;
		}
		if (begin<A.size() && A[begin]==target) return begin;
		return -1;
	}
};

// Method 2, using stl algorithm , Time 4279ms
class Solution {
public:
	/**
	 * @param A an integer array sorted in ascending order
	 * @param target an integer
	 * @return an integer
	 * Tip: See problem 14, first-position-of-target
	 */
	int findPosition(vector<int>& A, int target) {
		//Write your code here
		const auto &it=lower_bound(A.begin(),A.end(),target);
		if (it==A.end() || *it!=target) return -1;
		return it-A.begin();
	}
};
